// Package _0_Fib
// Date        : 2022/12/6 16:48
// Version     : 1.0.0
// Author      : 代码小学生王木木
// Email       : 18574945291@163.com
// Description :
package main

import "fmt"

//答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
// 0 1 2 3 4 5 6 ...
// 0 1 1 2 3 5 8...
func fib(n int) int {
	if n < 2 {
		return n
	}
	if n == 2 {
		return 1
	}
	const mod int = 1e9 + 7
	var ans int
	p, q := 1, 1
	for i := 2; i < n; i++ {
		ans = p + q
		p = q
		q = ans
	}
	return ans % mod
}

func main() {
	for i := 0; i < 10; i++ {
		fmt.Println(i, ":", fib(i))
	}
}
